package com.simon.study.algorithm.basic;

import java.util.Arrays;
import org.junit.Test;

/**
 * <p>
 *
 * @author simon
 * @date 2022/8/22 3:44 上午
 */
public class KthFind {
    @Test
    public void getKthNumber() {
        int[] bb = {1, 3, 8, 4, 7, 2, 1, 9, 10, 1, 5, 6};
        System.out.println(getKthNumber(bb, 5));
        System.out.println(Arrays.toString(bb));
    }


    public static int getKthNumber(int[] a, int k){
        int s = a.length;
        if(k > (s-1)){ return -1; }

        return quickSortKth(a, 0, s-1, k);
    }

    public static int quickSortKth(int[] a, int start, int end, int k) {
        if (start == end) { return start; }

        int t = start + (int)(Math.random() * (end-start));
        int ps = partitionKth(a, start, end, t);

        if(ps == k){ return a[k]; }
        else if(ps > k){ return quickSortKth(a, start, ps-1, k); }
        else{ return quickSortKth(a, ps+1, end, k); }
    }


    public static int partitionKth(int[] arr, int start, int end, int t){
        int ap = start, left = start, right = end, num = arr[t];

        while (ap <= right){
            if(arr[ap] < num && left++ < ap++){ swap(arr, left-1, ap-1); }
            else if(arr[ap] == num){ ap++; }
            else if(arr[ap] >  num){ if(ap==right){ break; } swap(arr, ap, right--); }
        }
        return left;
    }


    public static void swap(int[] arr, int i, int j){
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
